package com.wngbms;

import java.util.Deque;
import java.util.LinkedList;

public class BinaryTree {

    public static void main(String[] args) {
        Node root = new Node(1);

        pre(root);
        System.out.println();
        preWithoutRecursion(root);
        System.out.println();
//        mid(root);
//        post(root);
    }

    public static void postWithoutRecursion(Node root) {

        Deque<Node> res = new LinkedList<>();
        Deque<Node> q = new LinkedList<>();
        q.addFirst(root);


    }

    public static void preWithoutRecursion(Node root) {
        Deque<Node> q = new LinkedList<>();
        q.addFirst(root);

        while (!q.isEmpty()) {
            Node node = q.removeFirst();
            if (node == null) {
                return;
            }
            System.out.print(node.value + " ");
            if (node.right != null) {
                q.addFirst(node.right);
            }
            if (node.left != null) {
                q.addFirst(node.left);
            }
        }
    }

    public static void pre(Node root) {
        if (root == null) {
            return;
        }

        System.out.print(root.value + " ");
        pre(root.left);
        pre(root.right);
    }

    public static void mid(Node root) {
        if (root == null) {
            return;
        }

        mid(root.left);
        System.out.print(root.value + " ");
        mid(root.right);
    }

    public static void post(Node root) {
        if (root == null) {
            return;
        }

        post(root.left);
        post(root.right);
        System.out.print(root.value + " ");
    }

    public static class Node {
        int value;
        Node left;
        Node right;

        public Node(int val) {
            value = val;

            if (val <= 7) {
                left = new Node(val * 2);
                right = new Node(val * 2 + 1);
            }
        }
    }

}
